﻿
using System;

namespace AlgorithmDemo
{
    class Program
    {
        public const int theMax = int.MaxValue;
        public  const int Max = 4;
        public static int[,] D = new int[Max, Max] { { 0,5,theMax, 7 },
                                                     { theMax, 0, 4, 2 },
                                                     { 3, 3, 0, 2},
                                                     { theMax, theMax, 1, 0}};

        public static int[,] Path = new int[Max, Max] { { -1, 0,  -1,0},
                                                        { -1, -1, 1, 1},
                                                        {2, 2, -1, 2},
                                                        { -1, -1, 3, -1}
                                                       };

        public static int[,] maxSum = new int[Max,Max];
        public static int n = 100;

        public static int MaxSum(int i,int j)
        {
            if (maxSum[i,j] != -1)
                return maxSum[i,j];

            if (i == n-1)
            {
                maxSum[i, j] = D[i, j];
            }  
            else
            {
                int x = MaxSum(i+1,j);
                int y = MaxSum(i + 1, j + 1);
                if( x > y)
                {
                    Console.WriteLine($"i={i+1},j={j}");
                }
                else
                {
                    Console.WriteLine($"i={i + 1},j={j+1}");
                }
                maxSum[i, j] = Math.Max(x, y) + D[i, j];
            }

            return maxSum[i, j];
        }

        public static void Floyd()
        {
            for(int k=0;k< Max;k++)
            {
                for (int i = 0; i < Max; i++)
                {
                    for (int j = 0; j < Max; j++)
                    {
                        if (D[i, k] == int.MaxValue || D[k, j] == int.MaxValue)
                            continue;
                        if(D[i,j] > D[i,k]+D[k,j])
                        {
                            D[i, j] = D[i, k] + D[k, j];
                            Path[i, j] = k;
                        }
                    }
                }
            }
        }

        static void Main(string[] args)
        {
            Console.WriteLine($"-------{DateTime.Now.ToString()}");

            Floyd();
            n = 4;
            int i, j;
            var pStr = "";
            var str = "";
            for (i = 0; i < n; i++)
            {
                
                for (j = 0; j < n; j++)
                {
                    str += D[i, j] + ",";
                    pStr += Path[i, j] + ",";
                }

                pStr = pStr.Substring(0, pStr.Length-1) + "\n";
                str = str.Substring(0, str.Length - 1) + "\n";
                
            }
            Console.WriteLine(str);
            Console.WriteLine(pStr);
            /*------
            n = 5;

            int i, j;
            for (i = 0; i < n; i++)
            {
                for (j = 0; j <= i; j++)
                {
                    //D[i, j] = Console.Read();
                    maxSum[i, j] = -1;
                }
            }

            Console.WriteLine($"{MaxSum(0,0)}");

            i = n - 1;
            for(i=0; i<n;i++)
            {
                var str = "";
                for(j=0;j< n; j++)
                {
                    str += maxSum[i, j] + ",";
                }

                Console.WriteLine(str);
            }
            //foreach(var tt in maxSum)
            //{
            //    var tt
            //    Console.WriteLine(tt);
            //}
            */

            //Console.WriteLine(Fibonacci.foi(100));
            //Fibonacci.ToString();

            Console.WriteLine($"-------{DateTime.Now.ToString()}");
        }


    }
}
